Digital computers have long been used for solving various logical relationships and providing various manufacturing and process control functions. Typically, such computers approach the solution serially by sequentially performing various mathematical operations on numerical inputs. However, solution by direct computations on numerical inputs is inherently slow. For complicated mathematical functions with large number of inputs, direct calculation time becomes prohibitive.
Accordingly, various forms of special mathematical processors are known which can be used in conjunction with a standard digital computer to increase overall computational speed. Four well-known types of special processors include coprocessors, array processors, look-up tables and specialized programmable logical arrays, and an integrated system of a combination of ROMs, RAMs, programmable logical arrays, and logical circuitry.
A coprocessor, such as the Intel 8087, is a digital computer which operates in parallel with and under control of the main computer. The coprocessor can be programmed to perform floating point computational operations, such as addition, subtraction, multiplication and division, and selected trigonometric functions on two floating point binary numbers. The coprocessor generally performs only numerical calculations and overall computational speed is increased because complicated and time-consuming numerical computations can be performed simultaneously with other operations. However, within the coprocessor, the solution of complicated logical and numerical relationships are generally performed in the same manner as in the main computer--by serial calculations. Consequently, numerical computation speed for solving complicated logical and numerial relationships is still very slow.
Array processors are similar to coprocessors in that they operate in parallel with and under control of the main computer. However, unlike coprocessors, array processors are specifically designed to perform selected mathematical and some simple algebraic operations at high speed. Therefore, for simple calculations, array processors can operate much faster. However, for complicated calculations, the array processor must still perform time-consuming serial calculations.
Accordingly, attempts have been made to use look-up tables. A look-up table accepts a numerical input and uses that input to locate the desired result in a table. Since no serial calculations are performed, look-up tables operate at high-speed. Look-up tables are generally implemented in high-speed memories including ROMs, PROMs, EPROMs, EEPROMs and RAMs. The memory locations are first pre-programmed with the desired outputs of a function. During actual operation, the function inputs are provided to the address inputs of the memory. In the case of a ROM, application of an input pattern causes an output pattern to appear on the memory outputs. In the case of a RAM, the desired output is retrieved from the selected memory location and applied to the outputs.
A ROM for read only memory can be permanently programmed with a particular bit pattern, which is retained even after power is removed. Typically, a ROM includes input row lines connected by programmable connections to output column lines, with all of this structure being fabricated on a single integrated circuit chip. The ROM is programmed by selectively connecting input rows to output columns by opening or closing each connection point in a desired pattern. In general, any combinational truth table could be programmed into a ROM. Various forms of ROMs are presently known, according to their method of programming.
For example, mask-programming ROMs have the connection points and the resulting bit pattern built in at the time of manufacture. The obvious disadvantage with such devices is that, once programmed, the masked ROM can be used to solve only a fixed number of relationships and these relationships cannot be changed. Also, the masked ROM cannot be programmed by the user.
Programmable ROMs (PROMs) can be programmed by the user; once programmed, their pattern is permanent. This type of ROM is constructed with "fuse-links" at the internal connection points. The device is commonly programmed by electrically pulsing the ROM with current pulses. The current pulses selectively burn out not-wanted fuse-links to program the desired pattern into the ROM. PROMs suffer from the same disadvantage as masked ROMs in that once programmed, the PROM can be used to solve only a fixed number of relationships and these relationships cannot be thereafter changed.
Erasable programmable ROMs (EPROMs) are PROMs can be semi-permanently programmed in order to retain a desired bit pattern without the continuous application of power. However, such devices can be erased in order to re-program the memory at a later time. One type of EPROM uses transistors with insulted gates at the internal connection points. This type of EPROM can be programmed by selectively charging the insulated gates. The charge is retained for long periods of time and enables the associated transistor to close a connection at the associated connection point. The memory can be erased, if necessary, by exposing the memory chip to intense ultraviolet light thru a transparent quartz window covering the chip. The intense ultraviolet light causes the charge stored on the insulated gates to leak off, thereby opening all of the connections. Other types of EPROMs called electrically erasable programmable ROMs (EEPROMs) can be programmed and erased electrically, while connected in the circuit.
A typical RAM memory includes a plurality of row lines and a plurality of column lines. A multiple-bit register is connected at each intersection of the row lines and column lines with all of this structure being fabricated on a single integrated circuit chip. Each multiple-bit register is accessed by the coincidence of a row select signal and a column select signal. The row and column select signals are generated by decoding the applied address inputs and the contents of a selected register are applied to the device outputs. Two basic types of RAM memories include static RAMs and dynamic RAMs. A static RAM uses flip-flop devices to construct the multiple-bit registers, consequently, the data written into a static RAM remains until rewritten, unless the memory power is turned off. A dynamic RAM uses capacitors to construct the multiple-bit registers. Once charged, the capacitors discharge continuously and the stored data quickly disappears. Consequently, the charges on the capacitors must be continually refreshed or recharged by special memory refresh circuitry.
ROMs and RAMs are useful in many applications because they can operate at relatively high-speeds. Since no complicated calculations need to be carried out serially in order to generate an output in response to an arbitrary input, the solution speed is much faster than available from coprocessors and array processors. However, these devices have two basic drawbacks. First, they must be pre-programmed with a bit pattern that will generate the desired functional relationship between the inputs and outputs. The programming generally is not straightforward and requires a complete knowledge of memory construction and operation. Often special equipment is also required. Consequently, these devices are not suitable for general purpose use and are mainly suited for specialized applications where trained personnel are available for programming. Secondly, since each state or output of a function must be programmed as a memory location, for complicated functions or for simple functions with many inputs, the required number of memory locations becomes very large. In order to insure that the memories will operate properly, it is necessary to operatively test each memory location during manufacture. As the number of required memory locations grows, so does the testing time. For all but the simplest functions with small numbers of inputs, the memory test time quickly becomes prohibitive.
For example, these ROMs and RAMs have an unreasonable test time of 300+years for a 64 bit address. Each memory contains 2.sup.+ number of address bits data locations, which are accessed and tested one location at a time within one clock period. A ROM, RAM, programmable logic array, or gate array could could not reasonably be tested for all stored numbers with 64 address bits having 2.sup.+64 or about 10.sup.+19.2 data locations. Calculation: 2.sup.+64 equals 10.sup.+log 10.sup.2.times.64 or 10.sup.+0.3010.times.64 or 10.sup.+19.2. These 10.sup.+19.2 data locations would require 300+ years to test with a 1 GHz clock rate. Calculation for the 300+ years is: 2.sup.64 nanoseconds.times.(1 second/10.sup.+9 ns).times.(1 hour/3600 seconds).times.(1 day/24 hours).times.(1 year/365 days)=300+ years. This 300+ year test time is unreasonable. Testing of all address states is needed during manufacture to insure that the memory IC will operate correctly at a customer's location.
PLAs are similar to ROMs in that they operate at near look-up-table speed. Various forms of programmable logic arrays or PLAs are presently known. Typically, a PLA includes an input AND array connected by a substantial number of product or word lines to an output OR array, with all of this structure being fabricated on a single integrated circuit chip. Two known types of PLA's are mask programmable logic arrays (MPAs) and field programmable logic arrays (FPLAs). Mask programmable logic arrays are programmabled or personalized to perform a desired logic function only by altering the metalization mask used to fabricate the PLA integrated circuit chip. The making of such masks and the fabrication of the integrated circuit chips is a relatively expensive and time consuming process.
Field programmable logic arrays (FPLAs), on the other hand, are integrated circuit chips which contain complete sets of logic circuits, each of which is operatively connected to the array structure. Each such elemental logic circuit, however, includes a fuse link which can be electrically blown or burned out so as to disable that particular circuit. The user buys the chip with the complete array of circuits on it and then plugs it in to a special machine which he or she has programmed to burn out the fuseable links for the undesired circuits.
While useful in various applications, these field programmable logic arrays have various drawbacks. For example, these FPLAs are somewhat more expensive because of the need to provide the special fuseable links. Also, in order to make changes in the logic, a changed circuit requires a new chip and to burn in a completely new pattern. The old previously programmable chip or module cannot be used.
The disadvantage of the PLA or FPLA is that since the PLA can only be tested with input addresses as binary numbers, the test time of PLA with 64 input bits is 2.sup.+64 clock periods or 300+ years with a 1 GHz clock. This 300+ year test time is unreasonable. Typical test times are shown in Table 1.
TABLE 1 ______________________________________ Present Invention ______________________________________ Title: Test times for functions of various number of input parts. Clock is 1 GHz equal to 10.sup.+9 Hz. Input Address Test Time Parts States ______________________________________ 20 2.sup.+20 = 10.sup.+6.02 1- millisec. 32 2.sup.+32 = 10.sup.+9.632 4.3 seconds 64 2.sup.+64 = 10.sup.+19.264 300+ years 128 2.sup.+128 = 10.sup.+38.528 3+ billion trillion years ______________________________________
Another disadvantage of using PLAs or FPLAs with many inputs per each is the well known long time to reduce the number of boolean terms performed on sequencial computers, such as the long time of hours, days, weeks, and sometimes longer to process boolean terms of 32 parts or more.
A conventional computer, such as a mainframe vax 8600, will take too long to generate a set of lists. For example, the inventor of this invention ran a simple program to manipulate lists performing AND, OR, and list invert, which required 66 cpu hours or almost 3 days to run on a mainfram vax 8600 computer. At a commercal rate of $2,000 per cpu hour, 66 cpu hours would cost $132,000. By avoiding the exploration of pipelining, and generally unavailable parallel computers and supercomputers to convert mathematical functions and flowcharts to lists of boolean terms, this invention provides a design of a hardware logic code generator with needed mathematical concepts to allow rapid generation of sets of boolean lists.
A programmable gate array (PGA), such as the existing Xilinx gate array is programmed as a logic schematic or logic equations, and can operate about as fast as a ROM or RAM. The main limitations of PGAs are input/output test times are prohibitive for wide buses and the available computer-aided engineering (CAE) software to connect one or more PGAs in a circuit for arbitrary mathematical expressions does not exist. The basic purpose of PGAs is to replace small logic circuits, such as a simple floating point multiplier.
A Xilinx gate array is a programmable gate array of a propriety Logic Cell Array architecture. The Logic Cell Array (LCA) with an internal matrix of logic blocks and a surrounding ring of input/output interface blocks. Interconnect resources occupy the channels between the rows and columns of logic blocks, and between the logic blocks.
The core of the LCA is a matrix of identical Configurable Logic Blocks (CLBs). Each CLB contains programmable combinational logic and storage registers. The combinatorial logic section of the block is capable of implementing any Boolean function of 5 input variables. The registers can be loaded from the combinatorial logic or directly from a CLB input. The register outputs can be inputs to the combinatorial logic via an internal feedback path.
The periphery of the LCA is made up of user programmable input/Output Blocks (IOBs). Each block can be programmed independently to be an input, an output, or a bidirectional pin with three state control. Inputs can be programmed to recognize either TTL or CMOS electrical thresholds. Each IOB also includes flip-flops that can be used to buffer inputs and outputs.
The flexibility of the LCA is sue to resources that permit program control of the interconnection of any two points on the chip. Like other gate arrays, the LCA's interconnection resources include a two layer metal network of lines that run horizontally and vertically in the rows and columns between the CLBs to nearby metal lines. Crosspoint switches and interchanges at the intersections of rows and columns allow signals to be switched from one path to another. Long lines run the entire length or breadth of the chip, bypassing interchanges to provide distribution of critical signals with minimum delay or skew.
A serial configuration PROM is a necessary companion device that provides permanent storage of LCA configuration programs, usually activates after system power turn on.
A Xilinx gate array is a PGA that upon electrical power turn on is unprogrammed. A digital computer will activate the serial configuration PROM to send a code into the PGA to internal registers for logic circuit activation. The PGA can be reprogrammed with a new serial configuration code. When the power supply is removed, the PGA is unprogrammed. The serial configuration code was created in a CAE software product for only a certain size Xilinx PGA.
Design of a logic schematic of various circuits to operate as a arbitrary mathematical function is a labor intensive design engineering task by a skilled electronic engineer. Although CAE software can be used to create a small logic schematics, such as by Synopsys' CAE software, no means exists to automatically create a digital code to be programmed into one or more logic circuits to operate as an arbitrary mathematical function, such as
`output=log.sub.(a+b-c) ([c/b]-a)`, with output,a,b and c as buses of 32 floating point bits.
The PGA contains less gates than the first type or PROM, EPROM, EEPROM, RAM and second type or PLA, FPLA, but the PGA is usually slower due to more gate delays in series from input to output than the 3 to 8 gate delay of near look-up-table speed in the programmable IC circuits in this invention. The test time of the PGA is calculated the same as the ROM and is 300+ years for 64 input pins, unless internal macrocell outputs are accessable.
The design engineer programs a PGA only if the sub circuits or macrocells can each be tested by accessing the outputs of the utilized macrocells. Small PGAs are tested in small pieces and are usually 100% tested in a reasonable time.
Another disadvantage of existing gate arrays is that the PGA lacks high-speed in 3 to 8 gate delays.
An integrated system of a combination of ROMs, RAMs, PGAs, and logic circuitry, which operates as a group of sub circuits, can both process and be tested for 64 and any number of bit inputs. A test for a 64 bit by 64 bit floating point multiplier would be inputting 8 or 16 bits to a small part of the overall circuit and accessing an immediate output of the subcircuit.
The disadvantages of the integrated system are:
(1) a great many subcircuit outputs need to be accessed for even a two number operation on 64 bit binary numbers, and PA1 (2) the testing of all these subcircuits is quite complicated, due to the great many sub circuit outputs to be accessed. PA1 (3) the considerable number of gate delays from input to output. PA1 (1) no means exists to synthesize logic equations from arbitrary mathematical functions without using time consuming and usually unreasonable truth tables for programming into either mask or programmable circuitry. PA1 (2) no means exists to test all states for a complete circuit in a reasonable time, such as 10.sup.+19.2 data locations for 64 bit address or input, and PA1 (3) no means exists to process a spreadsheet at about 1 box per clock period, such as 10,000 boxes with each box to process a flow chart up to perhaps 10 trillion steps with many constraints for an arbitrary mathematical function with up to perhaps 25 variables of 32 bit resolution per variable, in a perhaps 100.times.100 box spread sheet as in Lotus 123.
The prior art, consisting of the four well-known types of special processors include coprocessors, array processors, look-up tables and specialized programmable logic arrays, and an integrated system of a combination of ROMs, RAMs, programmable logic arrays, and logic circuitry, has disadvantages, which are: